package lc;
import java.util.*;
import org.junit.*;
public class Ex442 {
    class Solution {
        public List<Integer> findDuplicates(int[] nums) {
            // 记录结果
            List<Integer> res = new ArrayList<>();
            
            int len = nums.length;
            
            // 特判
            if (len == 0){
                return res;
            }
    
            // 对数组自己做哈希：数值为i的数字映射到下标 i - 1的位置
            for (int i = 0; i < len; i++) {
                // 在指定范围内，如果数字并且没有放在正确的位置上，才交换
                // 例如：数值3应该放在索引2的位置上
                while (nums[nums[i] - 1] != nums[i]){
                    swap(nums,i,nums[i] - 1);
                }
            }
    
            // 遍历交换后的数组，如果当前下标和数字不对应
            // 说明出现了重复的数字，加入到res中
            for (int i = 0; i < len; i++) {
                if (nums[i] - 1 != i){
                    res.add(nums[i]);
                }
            }
            
            return res;
        }
    
        
        // 交换函数
        private void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = new int[]{4,3,2,7,8,2,3,1};
        System.out.println(s.findDuplicates(nums));
    }
}
